package com.atguigu.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author 龍
 * 逆波兰表达式十分的适合计算机进行计算。
 */
public class PolandNotation {
    public static void main(String[] args) {
        //先定义一个逆波兰表达式例如（3+4）*5-6  => 3 4 + 5 * 6 -
        String suffixExpression = "3 4 + 5 * 6 -";
        /*思路：
            1）先将"3 4 + 5 * 6 -"==>放到一个ArrayList中
            2）将ArrayList传递给一个方法，配合栈，遍历数组完成计算

         */
        List<String> rpnList = getListString(suffixExpression);
        System.out.println("rpnList=" + rpnList);
        int res = calculate(rpnList);
        System.out.println("计算器的结果：" + res);
        String expression = "1+((2+3)*4)-5";
        List<String> list = toInfixExpressionList(expression);
        System.out.println(list);
        System.out.println("===================================");
        List<String> polandNotation = toPolandNotation(list);
        System.out.println(polandNotation);
        System.out.println(calculate(polandNotation));
    }
    /**
     * 将一个逆波兰表达式，依次将数据和运算符放入到ArrayList中
     */
    public static List<String> getListString(String suffixExpression){
        String[] split=suffixExpression.split(" ");
        List<String> list=new ArrayList<String>();
        for (String ele:split) {
            list.add(ele);
        }
        return list;
    }
    /**
     * 完成对逆波兰表达式的计算
     * 1．从左至右扫描，将 3 和 4 压入堆栈；
     * 2．遇到+运算符，因此弹出 4 和 3（4 为栈顶元素，3 为次顶元素），计算出 3+4 的值，得 7，再将 7 入栈；
     * 3．将 5 入栈；
     * 4．接下来是×运算符，因此弹出 5 和 7，计算出 7×5=35，将 35 入栈；
     * 5．将 6 入栈；
     * 6．最后是-运算符，计算出 35-6 的值，即 29，由此得出最终结果
     *
     */
    public static int calculate(List<String> list){
        //创建一个栈，只需要一个栈即可
        Stack<String> stack = new Stack<String>();
        //遍历list
        for (String item : list) {
            //使用正则表达式来取出数字,代表匹配的为多位数
            if (item.matches("\\d+")){
                //入栈
                stack.push(item);
            }else {
                //pop出两个数，并进行运算
                int num2 =Integer.parseInt(stack.pop());
                int num1 =Integer.parseInt(stack.pop());
                int result=0;
                if (item.equals("+")){
                    result=num1+num2;
                }else if(item.equals("-")){
                    result=num1-num2;
                }else if(item.equals("*")){
                    result=num1*num2;
                }else if (item.equals("/")){
                    result=num1/num2;
                }else {
                    throw new RuntimeException("运算符不符合规范!!!");
                }
                //把res入栈,将结果转化为字符串
                stack.push(""+result);
            }
        }
        //最终留在stack中的就是最终的结果
        return Integer.parseInt(stack.pop());
    }
    /**
     * 将中缀表达式转换为后缀表达式:(3+4）*5-6
     * 注意：直接对字符串进行操作，不方便，因此先将字符串转换为list中的元素
     *
     */
    public static List<String> toInfixExpressionList(String s){
        //list
        ArrayList<String> strings = new ArrayList<String>();
        //指针
        int index=0;
        //对多位数进行拼接
        String str;
        //每遍历一个幅度就存放到c
        char c;
        do {
            //如果是一个非数字，放到strings
            if ((c=s.charAt(index))<48||(c=s.charAt(index))>57){
                strings.add(""+c);
                index++;
            }else{
                //如果是一个数，需要考虑多位数的问题
                str="";
                //注意此处的问题(&&和&的区别)
                while (index <s.length()&&(c=s.charAt(index))>=48&&(c=s.charAt(index))<=57){
                    str+=c;
                    index++;
                }
                strings.add(str);
            }
        }while (index <s.length());
            return strings;
    }
    /**
     * 将数组中的字符转换为逆波兰表达式：（3+4）*5-6
     * 1) 初始化两个栈：运算符栈 s1 和储存中间结果的栈 s2；
     * 2) 从左至右扫描中缀表达式；
     * 3) 遇到操作数时，将其压 s2；
     * 4) 遇到运算符时，比较其与 s1 栈顶运算符的优先级：
     * 1.如果 s1 为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
     * 2.否则，若优先级比栈顶运算符的高，也将运算符压入 s1；
     * 3.否则，将 s1 栈顶的运算符弹出并压入到 s2 中，再次转到(4-1)与 s1 中新的栈顶运算符相比较；
     * 5) 遇到括号时：
     * (1) 如果是左括号“(”，则直接压入 s1
     * (2) 如果是右括号“)”，则依次弹出 s1 栈顶的运算符，并压入 s2，直到遇到左括号为止，此时将这一对括号丢弃
     * 6) 重复步骤 2 至 5，直到表达式的最右边
     * 7) 将 s1 中剩余的运算符依次弹出并压入 s2
     * 8) 依次弹出 s2 中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
     *
     */
    public static List<String> toPolandNotation(List<String> expression){
        //初始化定义两个栈
        Stack<String> s1=new Stack<String>();
        //说明：s2这个栈，再整个转换的过程中，不存在pop操作，而且需要逆序的操作，我们直接使用list进行操作。
        ArrayList<String> s2 = new ArrayList<String>();
        for (int i = 0; i <expression.size(); i++) {
            //如果是一个数,直接加入s2
            if (expression.get(i).matches("\\d+")){
                s2.add(expression.get(i));
            }else if("(".equals(expression.get(i))){
                s1.push(expression.get(i));
            }else if (expression.get(i).equals(")")){
                while(!s1.peek().equals("(")){
                    s2.add(s1.pop());
                }
                //将“（”弹出，消除“（）”
                s1.pop();
            }else {
                //当expression的优先级小于等于栈顶的优先级，将s1栈顶的运算符加入到s2中
                //缺少比较优先级高低的方法
                while(s1.size()!=0&&Operation.getValue(s1.peek())>=Operation.getValue(expression.get(i))){
                    s2.add(s1.pop());
                }
                //将运算符压入到item中
                s1.push(expression.get(i));
            }
        }
        while (s1.size()!=0){
            s2.add(s1.pop());
        }
        //此时s2顺序输出即逆波兰表达式
        return s2;
    }
}
/**
 * 定义一个类，返回一个运算符的优先级
 */
class Operation{
    private static int ADD=1;
    private static int SUB=1;
    private static int MUL=2;
    private static int DIV=2;
    public static int getValue(String operation){
        int result=0;
        if ("+".equals(operation)){
            result=1;
        }else if("-".equals(operation)){
            result=1;
        }else if("*".equals(operation)){
            result=2;
        }else if("/".equals(operation)){
            result=2;
        }else{
            System.out.println("运算符不符合规范！！！");
        }
        return result;
    }
}